package foundation.graph;

import java.util.Scanner;

public class Floyd {
    static int MAXN = 1001;
    static int INF = Integer.MAX_VALUE;
    static int n;
    static int m;
    static int[][] dist = new int[MAXN][MAXN];

    /*
       枚举跳点
     */
    static void floyd() {
        for (int bridge = 1; bridge <= n; bridge++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    // i -> bridge -> j
                    // dist[i][j] 能否缩短
                    //dist[i][j] = min( dist[i][j] , dist[i][bridge] + dist[bridge][j] )
                    if (dist[i][bridge] != INF
                            && dist[bridge][j] != INF
                            && dist[i][j] > dist[i][bridge] + dist[bridge][j]) {
                        dist[i][j] = dist[i][bridge] + dist[bridge][j];
                    }
                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) dist[i][j] = 0;
                else dist[i][j] = INF;
            }
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            dist[u][v] = w;
            dist[v][u] = w;
        }
        floyd();
        System.out.println(dist[1][n]);
    }
}
